Programación Avanzada

1 Contenido de la clase

El problema de las 8 reinas

Enunciado: colocar 8 reinas en un tablero de ajedrez sin que se coman mutuamente. Las preguntas clásicas del backtracking son: ¿cuál es la primera solución?, ¿cuáles son todas las soluciones?, ¿cuál es la mejor solución?

Elementos del problema:

• Solución: 8 reinas colocadas en el tablero sin comerse mutuamente.
• Reglas: cualquier reina se puede colocar en cualquier lugar del tablero; una reina come en cualquier dirección y a cualquier distancia.
• Generar una solución parcial: colocar una reina en el tablero.

El material remite a ver el programa en Haskell y contrastarlo con otros lenguajes (por ejemplo Ocho reinas.c).

Historia del problema de las 8 reinas

• Propuesto originalmente en 1848 por el ajedrecista Max Friedrich William Bezzel.
• Muchos matemáticos famosos, incluyendo a Johann Carl Friedrich Gauss y a Georg Ferdinand Ludwig Philipp Cantor, trabajaron en él y lo generalizaron a n-reinas (tablero de n×n de tamaño arbitrario).
• Las primeras soluciones fueron propuestas por Franz Nauck en 1850, quien estudió también el problema de las n-reinas.
• En 1874, S. Günther propuso un método para hallar las soluciones usando determinantes, y J. W. L. Glaisher redefinió más tarde su propuesta.
• Edsger Dijkstra usó este problema en 1972 para ilustrar la programación estructurada; en ese mismo año publicó un artículo donde ilustra el algoritmo de backtracking.

Soluciones del problema de las 8 reinas

Según el programa (backtracking), existen 92 soluciones, de las cuales 12 son distintas: las otras 80 se obtienen a partir de simetrías, rotaciones y traslaciones de esas 12 soluciones únicas.

Los cuadros mágicos

Enunciado: colocar n números en un cuadro de n×n de tal manera que sumen lo mismo verticalmente, horizontalmente y diagonalmente. En la lámina se muestran el cuadro 3×3 (la suma es 15) y el cuadro 4×4 (la suma es 34). El material remite al documento Cuadros mágicos.pdf.

Historia:

• En la antigua China ya se conocían los cuadrados mágicos desde el III milenio a. C. (historia de una tortuga); también se conocen cuadros mágicos de egipcios, árabes y griegos.
• La introducción en occidente se atribuye a Emanuel Moschopoulos (bizantino, hoy Estambul, Turquía), investigador de la gramática del lenguaje en el siglo XIV, autor de un manuscrito con los primeros métodos para construirlos.
• Otros matemáticos famosos que los estudiaron: Pierre de Fermat, Blaise Pascal, Gottfried Wilhelm Leibniz y Leonhard Paul Euler.
• Aparecen en el cuadro "Melancolía I" (1514) de Alberto Durero y en la fachada de la Pasión del Templo Expiatorio de la Sagrada Familia (1882), en Barcelona. La constante mágica de ese cuadrado es 33, la edad de Jesucristo en la Pasión.

Preguntas del backtracking: ¿cuál es la primera solución? ¿cuáles son todas las soluciones?

• Para el cuadro mágico de tamaño 3 existe una única solución; las demás se obtienen por rotación o reflexión.
• En 1963, Bernard Frenicle de Bessy estableció que hay 880 cuadrados mágicos de tamaño 4.
• Posteriormente se ha encontrado que existen 275 305 224 cuadrados mágicos de tamaño 5.
• El número para tamaños mayores se desconoce aún; según estimaciones de Klaus Pinn y C. Wieczerkowski (1998), con métodos de Montecarlo y mecánica estadística, existen (1.7745 ± 0.0016) × 10^19 cuadrados de orden 6 y (3.7982 ± 0.0004) × 10^34 de orden 7.

Elementos del problema (para la mejor solución): solución = n números colocados en un cuadro de n×n que sumen lo mismo en vertical, horizontal y diagonal; reglas = cualquier número en cualquier lugar y un número ocupa solo un lugar; generar una solución parcial = colocar un número en el cuadrado.

Tarea de programación (cuadros mágicos)

La lámina pide como tarea realizar un programa en algún lenguaje imperativo que muestre todos los cuadros mágicos de tamaño n, donde n es leído por el programa (n = 3, 4 o 5, porque para tamaños mayores tarda demasiado).

Técnica de solución por patrones

Otra técnica de solución es la solución por patrones: encontrar un patrón en un conjunto de soluciones conocidas y replicarlo para generar otra solución. Ejemplos de la lámina: cuadro mágico de 4×4 y 8×8, y de 7×7 y 9×9.

Esta técnica ofrece soluciones más rápidas que el backtracking, incluso para cuadros de mayor tamaño. Para identificar el patrón (p. ej., la regla general de un cuadro 8×8 o 9×9) hay que ver el documento Cuadros mágicos.pdf.

2 Puntos destacados / Lo que hay que saber

3 Actividades y tareas pendientes

4 Dudas que podrían examinar

5 Sitios o recursos para visitar

• Problema de las ocho reinas — historia, soluciones (92 totales, 12 únicas) y generalización a n-reinas (dominio: google.com).
• Cuadrados mágicos — historia, métodos de construcción y conteo de soluciones por tamaño (dominio: google.com).
• Melancolía I (Durero, 1514) — obra que contiene un cuadrado mágico 4×4, citada en la historia de los cuadros mágicos (dominio: google.com).
• Edsger Dijkstra y las 8 reinas (1972) — uso del problema para ilustrar la programación estructurada y el backtracking (dominio: google.com).
• Bernard Frenicle de Bessy (1963) — quien estableció que hay 880 cuadrados mágicos de tamaño 4 (dominio: google.com).

6 Glosario de términos

• Backtracking: técnica de búsqueda exhaustiva que construye soluciones por etapas y retrocede cuando una vía no lleva a una solución válida
• Solución parcial: estado intermedio de la búsqueda; en las 8 reinas, colocar una reina; en los cuadros mágicos, colocar un número
• 8 reinas: problema de colocar 8 reinas en un tablero de ajedrez sin que se coman mutuamente
• n-reinas: generalización del problema a un tablero de n×n (Gauss y Cantor)
• Reina (ajedrez): pieza que come en cualquier dirección y a cualquier distancia
• Cuadro mágico (cuadrado mágico): colocación de n números en un cuadro de n×n que suman lo mismo en vertical, horizontal y diagonal
• Constante mágica: valor de la suma mágica del cuadrado (15 en 3×3, 34 en 4×4, 33 en el cuadrado de la Pasión)
• Rotación / reflexión: operaciones que convierten una solución única en las demás soluciones equivalentes (p. ej., cuadro 3×3)
• Simetría / rotación / traslación: operaciones que transforman las 12 soluciones únicas de las 8 reinas en las otras 80
• Montecarlo y mecánica estadística: métodos con los que Pinn y Wieczerkowski estimaron el número de cuadros mágicos de orden 6 y 7
• Técnica por patrones: encontrar un patrón en soluciones conocidas y replicarlo para generar otras soluciones (más rápido que el backtracking)

7 Mapa mental textual

• Programación Avanzada · Clase 3 — Backtracking aplicado: 8 reinas y cuadros mágicos, y solución por patrones
  • Problema de las 8 reinas
    • Enunciado y reglas (la reina come en cualquier dirección y distancia)
    • Historia: Bezzel 1848 · Gauss y Cantor (n-reinas) · Nauck 1850 · Günther 1874 (determinantes) · Glaisher · Dijkstra 1972
    • Soluciones: 92 totales · 12 únicas · 80 por simetrías/rotaciones/traslaciones
    • Programas: Haskell y Ocho reinas.c
  • Cuadros mágicos
    • Enunciado (sumar igual en vertical, horizontal y diagonal) · 3×3→15 · 4×4→34
    • Historia: China (III milenio a. C.) · Moschopoulos (s. XIV) · Fermat, Pascal, Leibniz, Euler · Durero (1514) · Sagrada Familia (1882, constante 33)
    • Conteo: 3×3 única · 4×4 = 880 (Frenicle 1963) · 5×5 = 275 305 224 · estimaciones orden 6 y 7 (Pinn y Wieczerkowski 1998)
    • Tarea: programa imperativo que muestre todos los cuadros de tamaño n (3, 4 o 5)
  • Solución por patrones
    • Replicar un patrón de soluciones conocidas
    • Ejemplos: 4×4↔8×8 y 7×7↔9×9 (ver Cuadros mágicos.pdf)
    • Más rápida que el backtracking